package com.da.javatest.niuke.other;

import java.util.HashMap;

/**
 * @author JokerDa.
 * @date 2021/12/16 15:48
 * Description:https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?
 * tpId=188&&tqId=38553&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
 */
public class NC41Solution {
    /**
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength(int[] arr) {
        if (arr.length < 2) {
            return arr.length;
        }

        HashMap<Integer, Integer> windows = new HashMap<>();
        int res = 0;
        //用双指针来模拟一个滑动窗口
        int left = -1;
        //窗口向右滑动
        for (int right = 0; right < arr.length; right++) {
            //遇到重复数字
            if (windows.containsKey(arr[right])) {
                //因为有可能遇到的重复数字的位置 比 left还要前
                //所以不能把left置于该位置前一位， 而是比较哪个最大，目的还是为了缩小窗口
                //确保窗口内全是不重复的数字
                left = Math.max(left, windows.get(arr[right]));
            }
            //每次更新窗口大小
            res = Math.max(res, right - left);
            //将数字位置更新到windows中
            windows.put(arr[right], right);
        }
        return res;
    }

    public static void main(String[] args) {
        NC41Solution test = new NC41Solution();
        System.out.println(test.maxLength(new int[] {1, 2, 3, 1, 2, 3, 3, 2, 1}));
    }
}
